There is a virtual storage system equipped with an address translation mechanism by means of hardware, and using a paging system capable of processing plural page sizes. In the virtual storage system, an address translation lookaside buffer (TLB) is used to perform an address translation from a virtual address (VA) to a physical address (PA) in high speed.
In the virtual storage system as stated above, it is performed to search page tables disposed at a main storage by respective page sizes when a TLB miss occurs in a memory access by a processor. Entries (address translation information) representing a correspondence between the virtual address and the physical address are stored in the page table. If the page table having an entry corresponding to the virtual address where the TLB miss occurs is found as a result of the search of the page table, the entry is registered to the TLB. On the other hand, when the page table having the corresponding entry is not found, the entry is registered to the TLB after the page table having the corresponding entry is prepared by means of software. For example, there are modes as illustrated in FIG. 6A and FIG. 6B as search modes of the page tables disposed at the main storage.
In the search mode illustrated in FIG. 6A, a base register BREG in which a base address for a pointer address generation is stored is held to search the page table disposed at the main storage. The base register BREG corresponds to a certain page size (a first page size), and a first base address BASE used for the search of the page table corresponding to the first page size is stored therein.
When the TLB miss occurs at the memory access time, a first pointer address PTA1 is generated from a part of a virtual address MVA where the TLB miss occurs and the first base address BASE stored at the base register BREG by a PTA generation process 101. The first pointer address PTA1 is a pointer address to search the page table corresponding to the first page size from the main storage. In a table search process 102, the page table corresponding to the first page size is read from a region of the address indicated by the first pointer address PTA1. When an entry corresponding to the virtual address MVA of the TLB miss is found from the read page table, the entry is registered to the TLB, a physical address PA1 corresponding to the virtual address MVA is output, and the address translation process by means of the hardware finishes.
On the other hand, when the entry corresponding to the virtual address MVA is not found from the read page table, a second pointer address PTA2 to search a page table corresponding to a second page size from the main storage is generated by a PTA generation process 103. Here, a second base address used for the search of the page table corresponding to the second page size is stored at a region of the address indicated by the first pointer address PTA1. In the PTA generation process 103, a second pointer address PTA2 is generated from the part of the virtual address MVA where the TLB miss occurs and the second base address.
In a table search process 104, the search of the page table corresponding to the second page size is performed as same as the case of the first page size by using the generated second pointer address PTA2. When the entry corresponding to the virtual address MVA of the TLB miss is found from the page table as a result of the search, the entry is registered to the TLB, a physical address PA2 corresponding to the virtual address MVA is output, and the address translation process finishes. Hereinafter, when the entry corresponding to the virtual address MVA of the TLB miss is not found, PTA generation processes 105, 107 and table search processes 106, 108 relating to each page size are sequentially performed until the corresponding entry is found.
In the search mode illustrated in FIG. 6A, the page table search for once is performed when the physical address corresponding to the virtual address MVA of the TLB miss is the physical address PA1, and the page table searches for twice are performed when it is the physical address PA2. Similarly, the page table searches for three times are performed when the physical address corresponding to the virtual address MVA of the TLB miss is a physical address PA3, and the page table searches for four times are performed when it is a physical address PA4. Accordingly, memory accesses for the number of times corresponding to the number of supported page sizes occur at the most for the page table searches in the search mode illustrated in FIG. 6A. Besides, it is impossible to control a search order of the page tables corresponding to the page sizes in the search mode illustrated in FIG. 6A.
In the search mode illustrated in FIG. 6B, the base registers each storing the base address for the pointer address generation are held for the number of supported page sizes to search the page tables disposed at the main storage. A valid bit V, the base address BASE, a page size PS, and a table size TS used for the search of the page table, and so on are stored at each of base registers B1REG, B2REG, B3REG, B4REG.
When the TLB miss occurs, a pointer address of the page table corresponding to the page size is generated from a part of the virtual address MVA where the TLB miss occurs and the base address BASE stored at one of the base registers by a PTA generation process 111. In a table search process 113, the page table is read from a region of the address indicated by the pointer address. When an entry corresponding to the virtual address MVA of the TLB miss is found from the read page table, the entry is registered to the TLB, a physical address corresponding to the virtual address MVA is output, and the address translation process by means of the hardware finishes.
On the other hand, when the entry corresponding to the virtual address MVA is not found from the read page table, the base address BASE is taken out from another base register. The pointer address of the page table corresponding to the page size is generated from the part of the virtual address MVA of the TLB miss and the base address BASE which is taken out this time by the PTA generation process 111. The page table is similarly searched from a region of the address indicated by the pointer address by the table search process 113 and the address translation process is performed.
In the search mode illustrated in FIG. 6B, it is performed to control whether the search of the page tables is performed sequentially or in parallel by a search order control mechanism 112. When the search of the page tables is performed sequentially, a priority order of information of which base register is to be used is fixed, and the search of the page tables corresponding to the page sizes is performed according to that order and is fixed. When the page table is searched sequentially, the address translation process finishes when the entry corresponding to the virtual address MVA of the TLB miss is registered to the searched page table without performing the search of the subsequent page tables. However, when the entry corresponding to the virtual address MVA of the TLB miss is not found in the searched page table, memory accesses for the number of times corresponding to the number of base registers occur at the most for the page table search. Besides, when the page tables are searched in parallel, the memory accesses for the number of base registers occur for the page table search. As stated above, in the search mode illustrated in FIG. 6B, the memory accesses for once to the number of valid base registers at the most occur for the page table search as for one TLB miss.
In the following Patent Document 1, a page management mode of a main storage in which a usage frequency counter counting a usage frequency of pages is held as for the main storage having pages of a certain size for “n” pages and an exchange of pages is performed in accordance with the usage frequency, is proposed.
[Patent Document 1] Japanese Laid-Open Patent Publication No. 05-40698
Here, the entry of the page table actually registered to the TLB and used as for one TLB miss is only one entry corresponding to the virtual address where the TLB miss occurs.
In the search mode illustrated in FIG. 6A, the address translation process finishes by the page table search (memory access) for once if the entry corresponding to the virtual address of the TLB miss exists at the page table searched by the first pointer address PTA1. However, when the entry corresponding to the virtual address of the TLB miss does not exist at the searched page table, the plural number of times of page table searches (memory accesses) are performed until the corresponding entry is found. Accordingly, there is a problem in which the memory accesses (requests) caused by a useless table fetch occur frequently. Besides, there is a problem in which a cache memory is contaminated because the entries of unnecessary page tables are registered to the cache memory. Further, there is a possibility in which the search is performed from the unnecessary page table, and a process time of the page table search increases.
Besides, in the search mode illustrated in FIG. 6B, there is a similar problem as the search mode illustrated in FIG. 6A if the search of the page table is performed sequentially. There are the problems in which the memory accesses (requests) caused by the useless table fetch occur frequently and the cache memory is contaminated because the entries of the unused page tables are registered to the cache memory even when the searches of the page tables are performed in parallel.